{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Assignment 3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1.复习课上内容及代码。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**1.1 寻找最优分割**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import defaultdict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defaultdict(int,\n",
       "            {1: 1,\n",
       "             2: 5,\n",
       "             3: 8,\n",
       "             4: 9,\n",
       "             5: 10,\n",
       "             6: 17,\n",
       "             7: 17,\n",
       "             8: 20,\n",
       "             9: 24,\n",
       "             10: 30,\n",
       "             11: 35})"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 长度为key米的钢材卖value元钱\n",
    "original_prica = [1, 5, 8, 9, 10, 17, 17, 20, 24, 30, 35]\n",
    "price = defaultdict(int)\n",
    "for i,p in enumerate(original_prica):\n",
    "    price[i+1] = p\n",
    "price    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 返回最大利润\n",
    "def r(n): \n",
    "    return max(\n",
    "        [price[n]] + [r(int(i)) + r(int(n-i)) for i in range(1,i//2+1)]\n",
    "        # 不切的利润     遍历所有切法的利润 \n",
    "    )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 不太懂递归的同学 可以用下面函数看递归过程\n",
    "def studey_r(n): # 返回最大利润\n",
    "    \n",
    "    cuts = [n]\n",
    "    cuts += [(i,n-i) for i in range(1,n//2+1)]\n",
    "    l = [price[n]] + [studey_r(i) + studey_r(n-i) for i in range(1,n//2+1)]\n",
    "        # 不切的利润     遍历所有切法的利润  \n",
    "    best = max(l)\n",
    "    i = l.index(best)\n",
    "    print(\"当 n={}, 有这些切法:{},对应的价格为:{},最好的切法为价格最高的即:{}\".format(n,cuts,l,([cuts[i]],best)))\n",
    "    return best"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=4, 有这些切法:[4, (1, 3), (2, 2)],对应的价格为:[9, 9, 10],最好的切法为价格最高的即:([(2, 2)], 10)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=5, 有这些切法:[5, (1, 4), (2, 3)],对应的价格为:[10, 11, 13],最好的切法为价格最高的即:([(2, 3)], 13)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=4, 有这些切法:[4, (1, 3), (2, 2)],对应的价格为:[9, 9, 10],最好的切法为价格最高的即:([(2, 2)], 10)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=6, 有这些切法:[6, (1, 5), (2, 4), (3, 3)],对应的价格为:[17, 14, 15, 16],最好的切法为价格最高的即:([6], 17)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=4, 有这些切法:[4, (1, 3), (2, 2)],对应的价格为:[9, 9, 10],最好的切法为价格最高的即:([(2, 2)], 10)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=5, 有这些切法:[5, (1, 4), (2, 3)],对应的价格为:[10, 11, 13],最好的切法为价格最高的即:([(2, 3)], 13)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=4, 有这些切法:[4, (1, 3), (2, 2)],对应的价格为:[9, 9, 10],最好的切法为价格最高的即:([(2, 2)], 10)\n",
      "当 n=7, 有这些切法:[7, (1, 6), (2, 5), (3, 4)],对应的价格为:[17, 18, 18, 18],最好的切法为价格最高的即:([(1, 6)], 18)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=4, 有这些切法:[4, (1, 3), (2, 2)],对应的价格为:[9, 9, 10],最好的切法为价格最高的即:([(2, 2)], 10)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=5, 有这些切法:[5, (1, 4), (2, 3)],对应的价格为:[10, 11, 13],最好的切法为价格最高的即:([(2, 3)], 13)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=4, 有这些切法:[4, (1, 3), (2, 2)],对应的价格为:[9, 9, 10],最好的切法为价格最高的即:([(2, 2)], 10)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=6, 有这些切法:[6, (1, 5), (2, 4), (3, 3)],对应的价格为:[17, 14, 15, 16],最好的切法为价格最高的即:([6], 17)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=4, 有这些切法:[4, (1, 3), (2, 2)],对应的价格为:[9, 9, 10],最好的切法为价格最高的即:([(2, 2)], 10)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=5, 有这些切法:[5, (1, 4), (2, 3)],对应的价格为:[10, 11, 13],最好的切法为价格最高的即:([(2, 3)], 13)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=4, 有这些切法:[4, (1, 3), (2, 2)],对应的价格为:[9, 9, 10],最好的切法为价格最高的即:([(2, 2)], 10)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=4, 有这些切法:[4, (1, 3), (2, 2)],对应的价格为:[9, 9, 10],最好的切法为价格最高的即:([(2, 2)], 10)\n",
      "当 n=8, 有这些切法:[8, (1, 7), (2, 6), (3, 5), (4, 4)],对应的价格为:[20, 19, 22, 21, 20],最好的切法为价格最高的即:([(2, 6)], 22)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=4, 有这些切法:[4, (1, 3), (2, 2)],对应的价格为:[9, 9, 10],最好的切法为价格最高的即:([(2, 2)], 10)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=5, 有这些切法:[5, (1, 4), (2, 3)],对应的价格为:[10, 11, 13],最好的切法为价格最高的即:([(2, 3)], 13)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=4, 有这些切法:[4, (1, 3), (2, 2)],对应的价格为:[9, 9, 10],最好的切法为价格最高的即:([(2, 2)], 10)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=6, 有这些切法:[6, (1, 5), (2, 4), (3, 3)],对应的价格为:[17, 14, 15, 16],最好的切法为价格最高的即:([6], 17)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=4, 有这些切法:[4, (1, 3), (2, 2)],对应的价格为:[9, 9, 10],最好的切法为价格最高的即:([(2, 2)], 10)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=5, 有这些切法:[5, (1, 4), (2, 3)],对应的价格为:[10, 11, 13],最好的切法为价格最高的即:([(2, 3)], 13)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=4, 有这些切法:[4, (1, 3), (2, 2)],对应的价格为:[9, 9, 10],最好的切法为价格最高的即:([(2, 2)], 10)\n",
      "当 n=7, 有这些切法:[7, (1, 6), (2, 5), (3, 4)],对应的价格为:[17, 18, 18, 18],最好的切法为价格最高的即:([(1, 6)], 18)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=4, 有这些切法:[4, (1, 3), (2, 2)],对应的价格为:[9, 9, 10],最好的切法为价格最高的即:([(2, 2)], 10)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=5, 有这些切法:[5, (1, 4), (2, 3)],对应的价格为:[10, 11, 13],最好的切法为价格最高的即:([(2, 3)], 13)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=4, 有这些切法:[4, (1, 3), (2, 2)],对应的价格为:[9, 9, 10],最好的切法为价格最高的即:([(2, 2)], 10)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=6, 有这些切法:[6, (1, 5), (2, 4), (3, 3)],对应的价格为:[17, 14, 15, 16],最好的切法为价格最高的即:([6], 17)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=4, 有这些切法:[4, (1, 3), (2, 2)],对应的价格为:[9, 9, 10],最好的切法为价格最高的即:([(2, 2)], 10)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=4, 有这些切法:[4, (1, 3), (2, 2)],对应的价格为:[9, 9, 10],最好的切法为价格最高的即:([(2, 2)], 10)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=5, 有这些切法:[5, (1, 4), (2, 3)],对应的价格为:[10, 11, 13],最好的切法为价格最高的即:([(2, 3)], 13)\n",
      "当 n=9, 有这些切法:[9, (1, 8), (2, 7), (3, 6), (4, 5)],对应的价格为:[24, 23, 23, 25, 23],最好的切法为价格最高的即:([(3, 6)], 25)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=4, 有这些切法:[4, (1, 3), (2, 2)],对应的价格为:[9, 9, 10],最好的切法为价格最高的即:([(2, 2)], 10)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=5, 有这些切法:[5, (1, 4), (2, 3)],对应的价格为:[10, 11, 13],最好的切法为价格最高的即:([(2, 3)], 13)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=4, 有这些切法:[4, (1, 3), (2, 2)],对应的价格为:[9, 9, 10],最好的切法为价格最高的即:([(2, 2)], 10)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=6, 有这些切法:[6, (1, 5), (2, 4), (3, 3)],对应的价格为:[17, 14, 15, 16],最好的切法为价格最高的即:([6], 17)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=4, 有这些切法:[4, (1, 3), (2, 2)],对应的价格为:[9, 9, 10],最好的切法为价格最高的即:([(2, 2)], 10)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=5, 有这些切法:[5, (1, 4), (2, 3)],对应的价格为:[10, 11, 13],最好的切法为价格最高的即:([(2, 3)], 13)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=4, 有这些切法:[4, (1, 3), (2, 2)],对应的价格为:[9, 9, 10],最好的切法为价格最高的即:([(2, 2)], 10)\n",
      "当 n=7, 有这些切法:[7, (1, 6), (2, 5), (3, 4)],对应的价格为:[17, 18, 18, 18],最好的切法为价格最高的即:([(1, 6)], 18)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=4, 有这些切法:[4, (1, 3), (2, 2)],对应的价格为:[9, 9, 10],最好的切法为价格最高的即:([(2, 2)], 10)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=5, 有这些切法:[5, (1, 4), (2, 3)],对应的价格为:[10, 11, 13],最好的切法为价格最高的即:([(2, 3)], 13)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=4, 有这些切法:[4, (1, 3), (2, 2)],对应的价格为:[9, 9, 10],最好的切法为价格最高的即:([(2, 2)], 10)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=6, 有这些切法:[6, (1, 5), (2, 4), (3, 3)],对应的价格为:[17, 14, 15, 16],最好的切法为价格最高的即:([6], 17)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=4, 有这些切法:[4, (1, 3), (2, 2)],对应的价格为:[9, 9, 10],最好的切法为价格最高的即:([(2, 2)], 10)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=5, 有这些切法:[5, (1, 4), (2, 3)],对应的价格为:[10, 11, 13],最好的切法为价格最高的即:([(2, 3)], 13)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=4, 有这些切法:[4, (1, 3), (2, 2)],对应的价格为:[9, 9, 10],最好的切法为价格最高的即:([(2, 2)], 10)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=4, 有这些切法:[4, (1, 3), (2, 2)],对应的价格为:[9, 9, 10],最好的切法为价格最高的即:([(2, 2)], 10)\n",
      "当 n=8, 有这些切法:[8, (1, 7), (2, 6), (3, 5), (4, 4)],对应的价格为:[20, 19, 22, 21, 20],最好的切法为价格最高的即:([(2, 6)], 22)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=4, 有这些切法:[4, (1, 3), (2, 2)],对应的价格为:[9, 9, 10],最好的切法为价格最高的即:([(2, 2)], 10)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=5, 有这些切法:[5, (1, 4), (2, 3)],对应的价格为:[10, 11, 13],最好的切法为价格最高的即:([(2, 3)], 13)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=4, 有这些切法:[4, (1, 3), (2, 2)],对应的价格为:[9, 9, 10],最好的切法为价格最高的即:([(2, 2)], 10)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=6, 有这些切法:[6, (1, 5), (2, 4), (3, 3)],对应的价格为:[17, 14, 15, 16],最好的切法为价格最高的即:([6], 17)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=4, 有这些切法:[4, (1, 3), (2, 2)],对应的价格为:[9, 9, 10],最好的切法为价格最高的即:([(2, 2)], 10)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=5, 有这些切法:[5, (1, 4), (2, 3)],对应的价格为:[10, 11, 13],最好的切法为价格最高的即:([(2, 3)], 13)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=4, 有这些切法:[4, (1, 3), (2, 2)],对应的价格为:[9, 9, 10],最好的切法为价格最高的即:([(2, 2)], 10)\n",
      "当 n=7, 有这些切法:[7, (1, 6), (2, 5), (3, 4)],对应的价格为:[17, 18, 18, 18],最好的切法为价格最高的即:([(1, 6)], 18)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=4, 有这些切法:[4, (1, 3), (2, 2)],对应的价格为:[9, 9, 10],最好的切法为价格最高的即:([(2, 2)], 10)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=4, 有这些切法:[4, (1, 3), (2, 2)],对应的价格为:[9, 9, 10],最好的切法为价格最高的即:([(2, 2)], 10)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=5, 有这些切法:[5, (1, 4), (2, 3)],对应的价格为:[10, 11, 13],最好的切法为价格最高的即:([(2, 3)], 13)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=4, 有这些切法:[4, (1, 3), (2, 2)],对应的价格为:[9, 9, 10],最好的切法为价格最高的即:([(2, 2)], 10)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=6, 有这些切法:[6, (1, 5), (2, 4), (3, 3)],对应的价格为:[17, 14, 15, 16],最好的切法为价格最高的即:([6], 17)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=4, 有这些切法:[4, (1, 3), (2, 2)],对应的价格为:[9, 9, 10],最好的切法为价格最高的即:([(2, 2)], 10)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=5, 有这些切法:[5, (1, 4), (2, 3)],对应的价格为:[10, 11, 13],最好的切法为价格最高的即:([(2, 3)], 13)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=4, 有这些切法:[4, (1, 3), (2, 2)],对应的价格为:[9, 9, 10],最好的切法为价格最高的即:([(2, 2)], 10)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=1, 有这些切法:[1],对应的价格为:[1],最好的切法为价格最高的即:([1], 1)\n",
      "当 n=2, 有这些切法:[2, (1, 1)],对应的价格为:[5, 2],最好的切法为价格最高的即:([2], 5)\n",
      "当 n=3, 有这些切法:[3, (1, 2)],对应的价格为:[8, 6],最好的切法为价格最高的即:([3], 8)\n",
      "当 n=5, 有这些切法:[5, (1, 4), (2, 3)],对应的价格为:[10, 11, 13],最好的切法为价格最高的即:([(2, 3)], 13)\n",
      "当 n=10, 有这些切法:[10, (1, 9), (2, 8), (3, 7), (4, 6), (5, 5)],对应的价格为:[30, 26, 27, 26, 27, 26],最好的切法为价格最高的即:([10], 30)\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "30"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "studey_r(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**1.2 装饰器**\n",
    "\n",
    "*计算运行时间*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "from functools import wraps   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fibonacci(n):\n",
    "    if n  <= 2:\n",
    "        return 1\n",
    "    else:\n",
    "        return fibonacci(n-1) + fibonacci(n-2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5702887\n",
      "1.2898945808410645\n"
     ]
    }
   ],
   "source": [
    "# 不使用装饰器，直接计算运行时间\n",
    "start = time.time()\n",
    "print(fibonacci(34))\n",
    "end = time.time()\n",
    "print(end-start)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 计算运行时间的装饰器\n",
    "def get_time(func):  #告诉我们一个函数使用的时间\n",
    "    # @wraps(func)\n",
    "    def wrapper(*args):\n",
    "        start = time.time()\n",
    "        func(*args)  #调用传入的func\n",
    "        end = time.time()\n",
    "        print('used time : {}'.format(end-start)) #func这个函数花费的时间\n",
    "    return wrapper"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[python使用装饰器来装饰递归函数](https://www.zhihu.com/question/36831068)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "@get_time\n",
    "def fibonacci(n):\n",
    "    def _fibonacci(n):\n",
    "        if n  <= 2:\n",
    "            return 1\n",
    "        else:\n",
    "            return _fibonacci(n-1) + _fibonacci(n-2)\n",
    "    return _fibonacci(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "used time : 1.35206937789917\n"
     ]
    }
   ],
   "source": [
    "fibonacci(34)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*使用内存存储中间计算结果*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 不使用装饰器\n",
    "mem = defaultdict()\n",
    "def fibonacci_op(n):\n",
    "    if n in mem:\n",
    "        return mem[n]\n",
    "    else: \n",
    "        if n <= 2:\n",
    "            mem[n] = 1\n",
    "            return n\n",
    "        else:\n",
    "            result = fibonacci_op(n-1) + fibonacci_op(n-2)\n",
    "            mem[n] = result\n",
    "            return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "60069305349389553485230328147938327637512711715756608464840282181455129135650222091469390025675153774400017329999201913237442705604269396320307472875615201445732224703698769576659949243423336511140255224283124\n",
      "0.0010008811950683594\n"
     ]
    }
   ],
   "source": [
    "start = time.time()\n",
    "print(fibonacci_op(1000))\n",
    "end = time.time()\n",
    "print(end-start)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 使用内存存储中间计算结果的装饰器\n",
    "def memo(f):\n",
    "    already_computed = {} #用来存储计算过的数值\n",
    "    @wraps(f)\n",
    "    def _wrap(arg):\n",
    "        if arg in already_computed:  #检测是否之前已经算过\n",
    "            result = already_computed[arg] #如果算过直接返回数值\n",
    "        else:\n",
    "            result = f(arg)              #如果没有算过 调用r函数来计算数值\n",
    "            already_computed[arg] = result #把结果存储到dic里面以供后面使用\n",
    "        return result\n",
    "    return _wrap"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [],
   "source": [
    "@get_time\n",
    "def fibonacci(n):\n",
    "    @memo\n",
    "    def _fibonacci(n):\n",
    "        if n  <= 2:\n",
    "            return 1\n",
    "        else:\n",
    "            return _fibonacci(n-1) + _fibonacci(n-2)\n",
    "    return _fibonacci(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "used time : 0.002992868423461914\n"
     ]
    }
   ],
   "source": [
    "fibonacci(1000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 装饰器用法 *"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [],
   "source": [
    "def f1(func):\n",
    "    def wrapper(*args,**kwargs):\n",
    "        print('Started')\n",
    "        func(*args,**kwargs)\n",
    "        print('Ended')\n",
    "    return wrapper"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [],
   "source": [
    "@f1\n",
    "def g(a):\n",
    "    print(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Started\n",
      "Hello\n",
      "Ended\n"
     ]
    }
   ],
   "source": [
    "g('Hello')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [],
   "source": [
    "# *arg 表示不限类型和数量的参数，*kwargs表示默认参数\n",
    "def k(*arg,**kwargs):\n",
    "    print(kwargs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'b': 5}\n"
     ]
    }
   ],
   "source": [
    "k(6,b=5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* wrapper 函数用法 *"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "wrapper decorator\n"
     ]
    }
   ],
   "source": [
    "# 不用 @wrapper 打印装饰器函数的名字和文字描述\n",
    "def my_decorator(func):\n",
    "    def wrapper(*args, **kwargs):\n",
    "        '''decorator'''\n",
    "        print('Calling decorated function...')\n",
    "        return func(*args, **kwargs)\n",
    "    return wrapper  \n",
    " \n",
    "@my_decorator \n",
    "def example():\n",
    "    \"\"\"Docstring\"\"\" \n",
    "    print('Called example function')\n",
    "print(example.__name__, example.__doc__)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "example Docstring\n"
     ]
    }
   ],
   "source": [
    "# 使用 wraps函数，打印装饰器封装的函数名字和用法\n",
    "def my_decorator(func):\n",
    "    @wraps(func)\n",
    "    def wrapper(*args, **kwargs):\n",
    "        '''decorator'''\n",
    "        print('Calling decorated function...')\n",
    "        return func(*args, **kwargs)\n",
    "    return wrapper \n",
    "\n",
    "@my_decorator \n",
    "def example():\n",
    "    \"\"\"Docstring\"\"\" \n",
    "    print('Called example function')\n",
    "print(example.__name__, example.__doc__)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**1.3 使用装饰器优化计算**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [],
   "source": [
    "# memo装饰器\n",
    "def memo(f):\n",
    "    already_computed = {} #用来存储计算过的数值\n",
    "    @wraps(f)\n",
    "    def _wrap(arg):\n",
    "        if arg in already_computed:  #检测是否之前已经算过\n",
    "            result = already_computed[arg] #如果算过直接返回数值\n",
    "        else:\n",
    "            result = f(arg)              #如果没有算过 调用r函数来计算数值\n",
    "            already_computed[arg] = result #把结果存储到dic里面以供后面使用\n",
    "        return result\n",
    "    return _wrap"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [],
   "source": [
    "solution = {}\n",
    "\n",
    "@memo\n",
    "def r(n):\n",
    "    \"\"\"\n",
    "    Args: n is the iron length\n",
    "    Return: the max revenue \n",
    "    \"\"\"\n",
    "    max_price, max_split = max(\n",
    "        [(price[n], 0)] + [(r(i) + r(n-i), i) for i in range(1, n)], key=lambda x: x[0]\n",
    "    )\n",
    "\n",
    "    solution[n] = (n - max_split, max_split)\n",
    "    \n",
    "    return max_price"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "60"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 20m钢材最多卖多少钱\n",
    "r(20)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defaultdict(int,\n",
       "            {1: 1,\n",
       "             2: 5,\n",
       "             3: 8,\n",
       "             4: 9,\n",
       "             5: 10,\n",
       "             6: 17,\n",
       "             7: 17,\n",
       "             8: 20,\n",
       "             9: 24,\n",
       "             10: 30,\n",
       "             11: 35,\n",
       "             15: 0,\n",
       "             14: 0,\n",
       "             13: 0,\n",
       "             12: 0,\n",
       "             20: 0,\n",
       "             19: 0,\n",
       "             18: 0,\n",
       "             17: 0,\n",
       "             16: 0})"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "price"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{1: (1, 0),\n",
       " 2: (2, 0),\n",
       " 3: (3, 0),\n",
       " 4: (2, 2),\n",
       " 5: (3, 2),\n",
       " 6: (6, 0),\n",
       " 7: (6, 1),\n",
       " 8: (6, 2),\n",
       " 9: (6, 3),\n",
       " 10: (10, 0),\n",
       " 11: (11, 0),\n",
       " 12: (11, 1),\n",
       " 13: (11, 2),\n",
       " 14: (11, 3),\n",
       " 15: (13, 2),\n",
       " 16: (14, 2),\n",
       " 17: (11, 6),\n",
       " 18: (17, 1),\n",
       " 19: (17, 2),\n",
       " 20: (17, 3)}"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 分割方案\n",
    "solution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**1.4 分析分割方案**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [],
   "source": [
    "def parse_solution(n):\n",
    "    left_split, right_split = solution[n]\n",
    "    \n",
    "    if right_split == 0: return [left_split]\n",
    "    \n",
    "    return parse_solution(left_split) + parse_solution(right_split)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[11, 6, 3]"
      ]
     },
     "execution_count": 67,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 20m钢材的分割方案\n",
    "parse_solution(20)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2.回答以下理论题目："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2.1 动态规划(DP)可以处理的问题有什么特点 ？"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. 该问题是一个以时间划分阶段的动态过程，或者可以人为引入时间因素把它视为多阶段决策过程；\n",
    "2. 该问题可以被分解为若干可重复执行的子问题；\n",
    "\n",
    "能采用动态规划求解的问题的一般要具有3个性质：\n",
    "\n",
    "1. 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。\n",
    "2. 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。\n",
    "3. 有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2.2 简单描述动态规划的几个步骤？"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. 分析最优解的性质，并描述最优解的结构特征。 \n",
    "\n",
    "2. 递归地定义一个最优解的值。 \n",
    "\n",
    "3. 以自底向上的方法（或自顶向下的备忘录法）计算一个最优解的值。\n",
    "\n",
    "4. 根据计算最优值时得到的信息，构造一个最优解。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2.3 编辑距离算法的迭代公式是什么？"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$ D[i,j] = min(D[i-1,j]+1, D[i,j-1]+1, D[i-1,j-1]+1/0) $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3.实践题"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3.1 完成编辑距离解码函数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [],
   "source": [
    "solution = {}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {},
   "outputs": [],
   "source": [
    "from functools import lru_cache"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [],
   "source": [
    "@lru_cache(maxsize=2**10)\n",
    "def edit_distance(string1, string2):\n",
    "    \n",
    "    if len(string1) == 0: return len(string2)\n",
    "    if len(string2) == 0: return len(string1)\n",
    "    \n",
    "    tail_s1 = string1[-1]\n",
    "    tail_s2 = string2[-1]\n",
    "    \n",
    "    candidates = [\n",
    "        (edit_distance(string1[:-1], string2) + 1, 'DEL {}'.format(tail_s1)),  \n",
    "        # string 1 delete tail\n",
    "        (edit_distance(string1, string2[:-1]) + 1, 'ADD {}'.format(tail_s2)),  \n",
    "        # string 1 add tail of string2\n",
    "    ]\n",
    "    \n",
    "    if tail_s1 == tail_s2:\n",
    "        both_forward = (edit_distance(string1[:-1], string2[:-1]) + 0, '')\n",
    "    else:\n",
    "        both_forward = (edit_distance(string1[:-1], string2[:-1]) + 1, 'SUB {} => {}'.format(tail_s1, tail_s2))\n",
    "\n",
    "    candidates.append(both_forward)\n",
    "    \n",
    "    min_distance, operation = min(candidates, key=lambda x: x[0])\n",
    "    \n",
    "    solution[(string1, string2)] = operation \n",
    "    \n",
    "    return min_distance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 77,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "edit_distance('ABCDECG','ABCCEF')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{('A', 'A'): '',\n",
       " ('A', 'AB'): 'ADD B',\n",
       " ('A', 'ABC'): 'ADD C',\n",
       " ('A', 'ABCC'): 'ADD C',\n",
       " ('A', 'ABCCE'): 'ADD E',\n",
       " ('A', 'ABCCEF'): 'ADD F',\n",
       " ('AB', 'A'): 'DEL B',\n",
       " ('AB', 'AB'): '',\n",
       " ('AB', 'ABC'): 'ADD C',\n",
       " ('AB', 'ABCC'): 'ADD C',\n",
       " ('AB', 'ABCCE'): 'ADD E',\n",
       " ('AB', 'ABCCEF'): 'ADD F',\n",
       " ('ABC', 'A'): 'DEL C',\n",
       " ('ABC', 'AB'): 'DEL C',\n",
       " ('ABC', 'ABC'): '',\n",
       " ('ABC', 'ABCC'): 'ADD C',\n",
       " ('ABC', 'ABCCE'): 'ADD E',\n",
       " ('ABC', 'ABCCEF'): 'ADD F',\n",
       " ('ABCD', 'A'): 'DEL D',\n",
       " ('ABCD', 'AB'): 'DEL D',\n",
       " ('ABCD', 'ABC'): 'DEL D',\n",
       " ('ABCD', 'ABCC'): 'SUB D => C',\n",
       " ('ABCD', 'ABCCE'): 'ADD E',\n",
       " ('ABCD', 'ABCCEF'): 'ADD F',\n",
       " ('ABCDE', 'A'): 'DEL E',\n",
       " ('ABCDE', 'AB'): 'DEL E',\n",
       " ('ABCDE', 'ABC'): 'DEL E',\n",
       " ('ABCDE', 'ABCC'): 'DEL E',\n",
       " ('ABCDE', 'ABCCE'): '',\n",
       " ('ABCDE', 'ABCCEF'): 'ADD F',\n",
       " ('ABCDEC', 'A'): 'DEL C',\n",
       " ('ABCDEC', 'AB'): 'DEL C',\n",
       " ('ABCDEC', 'ABC'): 'DEL C',\n",
       " ('ABCDEC', 'ABCC'): '',\n",
       " ('ABCDEC', 'ABCCE'): 'DEL C',\n",
       " ('ABCDEC', 'ABCCEF'): 'SUB C => F',\n",
       " ('ABCDECG', 'A'): 'DEL G',\n",
       " ('ABCDECG', 'AB'): 'DEL G',\n",
       " ('ABCDECG', 'ABC'): 'DEL G',\n",
       " ('ABCDECG', 'ABCC'): 'DEL G',\n",
       " ('ABCDECG', 'ABCCE'): 'DEL G',\n",
       " ('ABCDECG', 'ABCCEF'): 'DEL G'}"
      ]
     },
     "execution_count": 78,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "metadata": {},
   "outputs": [],
   "source": [
    "def parse_results():\n",
    "    (string1, string2) = list(solution.keys())[-1]\n",
    "    operation = 'from '+ string1 + ' to ' + string2 + ': '\n",
    "    for i in range(1,max(len(string1),len(string2))+1):\n",
    "        key = (string1[0:i],string2[0:i])\n",
    "        operation += solution[key] + ' '\n",
    "    return operation[0:-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'from ABCDECG to ABCCEF:    SUB D => C  SUB C => F DEL G'"
      ]
     },
     "execution_count": 98,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "parse_results()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3.2 完成拼音自动纠错代码"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如何在不带空格的时候完成自动修整？--> 如何完成拼音的自动分割？   \n",
    "###### 提示：使用第一节课提到的语言模型!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {},
   "outputs": [],
   "source": [
    "# pip install pinyin\n",
    "import pinyin,re\n",
    "from collections import Counter, defaultdict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {},
   "outputs": [],
   "source": [
    "chinese_dataset = 'article_9k.txt'\n",
    "CHINESE_CHARATERS = open(chinese_dataset, encoding='utf-8').read()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 转为拼音\n",
    "def chinese_to_pinyin(character):\n",
    "    return pinyin.get(character, format='strip', delimiter=' ')\n",
    "\n",
    "CHINESE_CHARATERS_COPYS = chinese_to_pinyin(CHINESE_CHARATERS)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 174,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 拼音计数\n",
    "def tokens(text):\n",
    "    \"List all the pinyin characters\"\n",
    "    return re.findall('[a-z]+',text.lower())\n",
    "PINYIN_TOKEN = tokens(CHINESE_CHARATERS_COPYS)\n",
    "PINYIN_COUNT = Counter(PINYIN_TOKEN)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "metadata": {},
   "outputs": [],
   "source": [
    "#计算与 word 编辑距离为0的词\n",
    "def edits0(word):\n",
    "    'Return all strings that are zero edits away from word (i.e., just word itself).'\n",
    "    return {word}\n",
    "\n",
    "#计算与 word 编辑距离为1的词\n",
    "def splits(word):\n",
    "    'Return a list of all possible (first, rest) pairs that comprise pinyin.'\n",
    "    return [(word[:i], word[i:])\n",
    "           for i in range(len(word)+1)]\n",
    "\n",
    "alphabet = 'abcdefghijklmnopqrstuvwxyz'\n",
    "def edits1(word):\n",
    "    'Return all strings that are one edit away from this pinyin.'\n",
    "    pairs = splits(word)   \n",
    "    deletes = [a+b[1:] for (a,b) in pairs if b] # input pinyin -删除操作 去掉b[0]\n",
    "    replaces = [a+c+b[1:] for (a,b) in pairs for c in alphabet if b] #替换  b[0]替换为c\n",
    "    inserts = [a+c+b for (a,b) in pairs for c in alphabet] #插入操作 在a和b之间插入字母\n",
    "    return set(deletes + replaces + inserts)\n",
    "\n",
    "#计算与 word 编辑距离为2的词 \n",
    "# 可以通过计算与原词编辑距离为1的词的编辑距离为1的词\n",
    "def edits2(word):\n",
    "    'Return all strings that are two edits away from this pinyin.'\n",
    "    return {e2 for e1 in edits1(word) for e2 in edits1(e1)} "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 返回在拼音库中的词\n",
    "def known(words):\n",
    "    'Return the pinyin in our data'\n",
    "    return {w for w in words if w in PINYIN_COUNT}\n",
    "\n",
    "# 纠正单个拼音 word，在拼音库中查找与其编辑距离为1/2的最高频词\n",
    "def correct(word): #pinyin candidates piyin pingyin aogyin .... \n",
    "    'Find the most possible pinyin based on edit distance'\n",
    "    # Prefer edit distance 0, then 1, then 2; otherwist default to word itself\n",
    "    candidates = (known(edits0(word)) or\n",
    "                  known(edits1(word)) or\n",
    "                  known(edits2(word)) or\n",
    "                  [word])  #计算所有与输入词编辑距离为0，1，2的词\n",
    "    return max(candidates,key=PINYIN_COUNT.get) #取出在所有candidate里在语料库里出现次数最多的词"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 纠正一串带空格的拼音序列\n",
    "def correct_sequence_pinyin(text_pinyin):\n",
    "    return ' '.join(map(correct, text_pinyin.split()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 141,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'zhe si yi ge ce shi'"
      ]
     },
     "execution_count": 141,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "correct_sequence_pinyin('zhe sih yi ge ce sho')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 142,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'wo xiang shan qing hua da xue'"
      ]
     },
     "execution_count": 142,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "correct_sequence_pinyin('wo xiang shagn qinng hua da xue')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**1. 字符串查找所有拼音**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 191,
   "metadata": {},
   "outputs": [],
   "source": [
    "pinyin_file = open('pinyin_all.txt').read()\n",
    "pinyin_all = pinyin_file.split('\\n')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 192,
   "metadata": {
    "collapsed": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['a',\n",
       " 'ai',\n",
       " 'an',\n",
       " 'ang',\n",
       " 'ao',\n",
       " 'ba',\n",
       " 'bai',\n",
       " 'ban',\n",
       " 'bang',\n",
       " 'bao',\n",
       " 'bei',\n",
       " 'ben',\n",
       " 'beng',\n",
       " 'bi',\n",
       " 'bian',\n",
       " 'biao',\n",
       " 'bie',\n",
       " 'bin',\n",
       " 'bing',\n",
       " 'bo',\n",
       " 'bu',\n",
       " 'ca',\n",
       " 'cai',\n",
       " 'can',\n",
       " 'cang',\n",
       " 'cao',\n",
       " 'ce',\n",
       " 'cen',\n",
       " 'ceng',\n",
       " 'cha',\n",
       " 'chai',\n",
       " 'chan',\n",
       " 'chang',\n",
       " 'chao',\n",
       " 'che',\n",
       " 'chen',\n",
       " 'cheng',\n",
       " 'chi',\n",
       " 'chong',\n",
       " 'chou',\n",
       " 'chu',\n",
       " 'chua',\n",
       " 'chuai',\n",
       " 'chuan',\n",
       " 'chuang',\n",
       " 'chui',\n",
       " 'chun',\n",
       " 'chuo',\n",
       " 'ci',\n",
       " 'cong',\n",
       " 'cou',\n",
       " 'cu',\n",
       " 'cuan',\n",
       " 'cui',\n",
       " 'cun',\n",
       " 'cuo',\n",
       " 'da',\n",
       " 'dai',\n",
       " 'dan',\n",
       " 'dang',\n",
       " 'dao',\n",
       " 'de',\n",
       " 'dei',\n",
       " 'den',\n",
       " 'deng',\n",
       " 'di',\n",
       " 'dia',\n",
       " 'dian',\n",
       " 'diao',\n",
       " 'die',\n",
       " 'ding',\n",
       " 'diu',\n",
       " 'dong',\n",
       " 'dou',\n",
       " 'du',\n",
       " 'duan',\n",
       " 'dui',\n",
       " 'dun',\n",
       " 'duo',\n",
       " 'e',\n",
       " 'en',\n",
       " 'eng',\n",
       " 'er',\n",
       " 'fa',\n",
       " 'fan',\n",
       " 'fang',\n",
       " 'fei',\n",
       " 'fen',\n",
       " 'feng',\n",
       " 'fiao',\n",
       " 'fo',\n",
       " 'fou',\n",
       " 'fu',\n",
       " 'ga',\n",
       " 'gai',\n",
       " 'gan',\n",
       " 'gang',\n",
       " 'gao',\n",
       " 'ge',\n",
       " 'gei',\n",
       " 'gen',\n",
       " 'geng',\n",
       " 'gong',\n",
       " 'gou',\n",
       " 'gu',\n",
       " 'gua',\n",
       " 'guai',\n",
       " 'guan',\n",
       " 'guang',\n",
       " 'gui',\n",
       " 'gun',\n",
       " 'guo',\n",
       " 'ha',\n",
       " 'hai',\n",
       " 'han',\n",
       " 'hang',\n",
       " 'hao',\n",
       " 'he',\n",
       " 'hei',\n",
       " 'hen',\n",
       " 'heng',\n",
       " 'hong',\n",
       " 'hou',\n",
       " 'hu',\n",
       " 'hua',\n",
       " 'huai',\n",
       " 'huan',\n",
       " 'huang',\n",
       " 'hui',\n",
       " 'hun',\n",
       " 'huo',\n",
       " 'ji',\n",
       " 'jia',\n",
       " 'jian',\n",
       " 'jiang',\n",
       " 'jiao',\n",
       " 'jie',\n",
       " 'jin',\n",
       " 'jing',\n",
       " 'jiong',\n",
       " 'jiu',\n",
       " 'ju',\n",
       " 'juan',\n",
       " 'jue',\n",
       " '#NAME',\n",
       " 'ka',\n",
       " 'kai',\n",
       " 'kan',\n",
       " 'kang',\n",
       " 'kao',\n",
       " 'ke',\n",
       " 'ken',\n",
       " 'keng',\n",
       " 'kong',\n",
       " 'kou',\n",
       " 'ku',\n",
       " 'kua',\n",
       " 'kuai',\n",
       " 'kuan',\n",
       " 'kuang',\n",
       " 'kui',\n",
       " 'kun',\n",
       " 'kuo',\n",
       " 'la',\n",
       " 'lai',\n",
       " 'lan',\n",
       " 'lang',\n",
       " 'lao',\n",
       " 'le',\n",
       " 'lei',\n",
       " 'leng',\n",
       " 'li',\n",
       " 'lia',\n",
       " 'lian',\n",
       " 'liang',\n",
       " 'liao',\n",
       " 'lie',\n",
       " 'lin',\n",
       " 'ling',\n",
       " 'liu',\n",
       " 'lo',\n",
       " 'long',\n",
       " 'lou',\n",
       " 'lu',\n",
       " 'luan',\n",
       " 'lun',\n",
       " 'luo',\n",
       " 'lv',\n",
       " 'lve',\n",
       " 'ma',\n",
       " 'mai',\n",
       " 'man',\n",
       " 'mang',\n",
       " 'mao',\n",
       " 'me',\n",
       " 'mei',\n",
       " 'men',\n",
       " 'meng',\n",
       " 'mi',\n",
       " 'mian',\n",
       " 'miao',\n",
       " 'mie',\n",
       " 'min',\n",
       " 'ming',\n",
       " 'miu',\n",
       " 'mo',\n",
       " 'mou',\n",
       " 'mu',\n",
       " 'na',\n",
       " 'nai',\n",
       " 'nan',\n",
       " 'nang',\n",
       " 'nao',\n",
       " 'ne',\n",
       " 'nei',\n",
       " 'nen',\n",
       " 'neng',\n",
       " 'ni',\n",
       " 'nian',\n",
       " 'niang',\n",
       " 'niao',\n",
       " 'nie',\n",
       " 'nin',\n",
       " 'ning',\n",
       " 'niu',\n",
       " 'nong',\n",
       " 'nou',\n",
       " 'nu',\n",
       " 'nuan',\n",
       " 'nun',\n",
       " 'nuo',\n",
       " 'nv',\n",
       " 'nve',\n",
       " 'o',\n",
       " 'ou',\n",
       " 'pa',\n",
       " 'pai',\n",
       " 'pan',\n",
       " 'pang',\n",
       " 'pao',\n",
       " 'pei',\n",
       " 'pen',\n",
       " 'peng',\n",
       " 'pi',\n",
       " 'pian',\n",
       " 'piao',\n",
       " 'pie',\n",
       " 'pin',\n",
       " 'ping',\n",
       " 'po',\n",
       " 'pou',\n",
       " 'pu',\n",
       " 'qi',\n",
       " 'qia',\n",
       " 'qian',\n",
       " 'qiang',\n",
       " 'qiao',\n",
       " 'qie',\n",
       " 'qin',\n",
       " 'qing',\n",
       " 'qiong',\n",
       " 'qiu',\n",
       " 'qu',\n",
       " 'quan',\n",
       " 'que',\n",
       " 'qun',\n",
       " 'ran',\n",
       " 'rang',\n",
       " 'rao',\n",
       " 're',\n",
       " 'ren',\n",
       " 'reng',\n",
       " 'ri',\n",
       " 'rong',\n",
       " 'rou',\n",
       " 'ru',\n",
       " 'rua',\n",
       " 'ruan',\n",
       " 'rui',\n",
       " 'run',\n",
       " 'ruo',\n",
       " 'sa',\n",
       " 'sai',\n",
       " 'san',\n",
       " 'sang',\n",
       " 'sao',\n",
       " 'se',\n",
       " 'sen',\n",
       " 'seng',\n",
       " 'sha',\n",
       " 'shai',\n",
       " 'shan',\n",
       " 'shang',\n",
       " 'shao',\n",
       " 'she',\n",
       " 'shei',\n",
       " 'shen',\n",
       " 'sheng',\n",
       " 'shi',\n",
       " 'shou',\n",
       " 'shu',\n",
       " 'shua',\n",
       " 'shuai',\n",
       " 'shuan',\n",
       " 'shuang',\n",
       " 'shui',\n",
       " 'shun',\n",
       " 'shuo',\n",
       " 'si',\n",
       " 'song',\n",
       " 'sou',\n",
       " 'su',\n",
       " 'suan',\n",
       " 'sui',\n",
       " 'sun',\n",
       " 'suo',\n",
       " 'ta',\n",
       " 'tai',\n",
       " 'tan',\n",
       " 'tang',\n",
       " 'tao',\n",
       " 'te',\n",
       " 'tei',\n",
       " 'teng',\n",
       " 'ti',\n",
       " 'tian',\n",
       " 'tiao',\n",
       " 'tie',\n",
       " 'ting',\n",
       " 'tong',\n",
       " 'tou',\n",
       " 'tu',\n",
       " 'tuan',\n",
       " 'tui',\n",
       " 'tun',\n",
       " 'tuo',\n",
       " 'wa',\n",
       " 'wai',\n",
       " 'wan',\n",
       " 'wang',\n",
       " 'wei',\n",
       " 'wen',\n",
       " 'weng',\n",
       " 'wo',\n",
       " 'wu',\n",
       " 'xi',\n",
       " 'xia',\n",
       " 'xian',\n",
       " 'xiang',\n",
       " 'xiao',\n",
       " 'xie',\n",
       " 'xin',\n",
       " 'xing',\n",
       " 'xiong',\n",
       " 'xiu',\n",
       " 'xu',\n",
       " 'xuan',\n",
       " 'xue',\n",
       " 'xun',\n",
       " 'ya',\n",
       " 'yan',\n",
       " 'yang',\n",
       " 'yao',\n",
       " 'ye',\n",
       " 'yi',\n",
       " 'yin',\n",
       " 'ying',\n",
       " 'yo',\n",
       " 'yong',\n",
       " 'you',\n",
       " 'yu',\n",
       " 'yuan',\n",
       " 'yue',\n",
       " 'yun',\n",
       " 'za',\n",
       " 'zai',\n",
       " 'zan',\n",
       " 'zang',\n",
       " 'zao',\n",
       " 'ze',\n",
       " 'zei',\n",
       " 'zen',\n",
       " 'zeng',\n",
       " 'zha',\n",
       " 'zhai',\n",
       " 'zhan',\n",
       " 'zhang',\n",
       " 'zhao',\n",
       " 'zhe',\n",
       " 'zhei',\n",
       " 'zhen',\n",
       " 'zheng',\n",
       " 'zhi',\n",
       " 'zhong',\n",
       " 'zhou',\n",
       " 'zhu',\n",
       " 'zhua',\n",
       " 'zhuai',\n",
       " 'zhuan',\n",
       " 'zhuang',\n",
       " 'zhui',\n",
       " 'zhun',\n",
       " 'zhuo',\n",
       " 'zi',\n",
       " 'zong',\n",
       " 'zou',\n",
       " 'zu',\n",
       " 'zuan',\n",
       " 'zui',\n",
       " 'zun',\n",
       " 'zuo']"
      ]
     },
     "execution_count": 192,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pinyin_all"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 202,
   "metadata": {},
   "outputs": [],
   "source": [
    "pinyin_all.sort(key = lambda i:len(i),reverse=True) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 203,
   "metadata": {
    "collapsed": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['chuang',\n",
       " 'shuang',\n",
       " 'zhuang',\n",
       " 'chang',\n",
       " 'cheng',\n",
       " 'chong',\n",
       " 'chuai',\n",
       " 'chuan',\n",
       " 'guang',\n",
       " 'huang',\n",
       " 'jiang',\n",
       " 'jiong',\n",
       " '#NAME',\n",
       " 'kuang',\n",
       " 'liang',\n",
       " 'niang',\n",
       " 'qiang',\n",
       " 'qiong',\n",
       " 'shang',\n",
       " 'sheng',\n",
       " 'shuai',\n",
       " 'shuan',\n",
       " 'xiang',\n",
       " 'xiong',\n",
       " 'zhang',\n",
       " 'zheng',\n",
       " 'zhong',\n",
       " 'zhuai',\n",
       " 'zhuan',\n",
       " 'bang',\n",
       " 'beng',\n",
       " 'bian',\n",
       " 'biao',\n",
       " 'bing',\n",
       " 'cang',\n",
       " 'ceng',\n",
       " 'chai',\n",
       " 'chan',\n",
       " 'chao',\n",
       " 'chen',\n",
       " 'chou',\n",
       " 'chua',\n",
       " 'chui',\n",
       " 'chun',\n",
       " 'chuo',\n",
       " 'cong',\n",
       " 'cuan',\n",
       " 'dang',\n",
       " 'deng',\n",
       " 'dian',\n",
       " 'diao',\n",
       " 'ding',\n",
       " 'dong',\n",
       " 'duan',\n",
       " 'fang',\n",
       " 'feng',\n",
       " 'fiao',\n",
       " 'gang',\n",
       " 'geng',\n",
       " 'gong',\n",
       " 'guai',\n",
       " 'guan',\n",
       " 'hang',\n",
       " 'heng',\n",
       " 'hong',\n",
       " 'huai',\n",
       " 'huan',\n",
       " 'jian',\n",
       " 'jiao',\n",
       " 'jing',\n",
       " 'juan',\n",
       " 'kang',\n",
       " 'keng',\n",
       " 'kong',\n",
       " 'kuai',\n",
       " 'kuan',\n",
       " 'lang',\n",
       " 'leng',\n",
       " 'lian',\n",
       " 'liao',\n",
       " 'ling',\n",
       " 'long',\n",
       " 'luan',\n",
       " 'mang',\n",
       " 'meng',\n",
       " 'mian',\n",
       " 'miao',\n",
       " 'ming',\n",
       " 'nang',\n",
       " 'neng',\n",
       " 'nian',\n",
       " 'niao',\n",
       " 'ning',\n",
       " 'nong',\n",
       " 'nuan',\n",
       " 'pang',\n",
       " 'peng',\n",
       " 'pian',\n",
       " 'piao',\n",
       " 'ping',\n",
       " 'qian',\n",
       " 'qiao',\n",
       " 'qing',\n",
       " 'quan',\n",
       " 'rang',\n",
       " 'reng',\n",
       " 'rong',\n",
       " 'ruan',\n",
       " 'sang',\n",
       " 'seng',\n",
       " 'shai',\n",
       " 'shan',\n",
       " 'shao',\n",
       " 'shei',\n",
       " 'shen',\n",
       " 'shou',\n",
       " 'shua',\n",
       " 'shui',\n",
       " 'shun',\n",
       " 'shuo',\n",
       " 'song',\n",
       " 'suan',\n",
       " 'tang',\n",
       " 'teng',\n",
       " 'tian',\n",
       " 'tiao',\n",
       " 'ting',\n",
       " 'tong',\n",
       " 'tuan',\n",
       " 'wang',\n",
       " 'weng',\n",
       " 'xian',\n",
       " 'xiao',\n",
       " 'xing',\n",
       " 'xuan',\n",
       " 'yang',\n",
       " 'ying',\n",
       " 'yong',\n",
       " 'yuan',\n",
       " 'zang',\n",
       " 'zeng',\n",
       " 'zhai',\n",
       " 'zhan',\n",
       " 'zhao',\n",
       " 'zhei',\n",
       " 'zhen',\n",
       " 'zhou',\n",
       " 'zhua',\n",
       " 'zhui',\n",
       " 'zhun',\n",
       " 'zhuo',\n",
       " 'zong',\n",
       " 'zuan',\n",
       " 'ang',\n",
       " 'bai',\n",
       " 'ban',\n",
       " 'bao',\n",
       " 'bei',\n",
       " 'ben',\n",
       " 'bie',\n",
       " 'bin',\n",
       " 'cai',\n",
       " 'can',\n",
       " 'cao',\n",
       " 'cen',\n",
       " 'cha',\n",
       " 'che',\n",
       " 'chi',\n",
       " 'chu',\n",
       " 'cou',\n",
       " 'cui',\n",
       " 'cun',\n",
       " 'cuo',\n",
       " 'dai',\n",
       " 'dan',\n",
       " 'dao',\n",
       " 'dei',\n",
       " 'den',\n",
       " 'dia',\n",
       " 'die',\n",
       " 'diu',\n",
       " 'dou',\n",
       " 'dui',\n",
       " 'dun',\n",
       " 'duo',\n",
       " 'eng',\n",
       " 'fan',\n",
       " 'fei',\n",
       " 'fen',\n",
       " 'fou',\n",
       " 'gai',\n",
       " 'gan',\n",
       " 'gao',\n",
       " 'gei',\n",
       " 'gen',\n",
       " 'gou',\n",
       " 'gua',\n",
       " 'gui',\n",
       " 'gun',\n",
       " 'guo',\n",
       " 'hai',\n",
       " 'han',\n",
       " 'hao',\n",
       " 'hei',\n",
       " 'hen',\n",
       " 'hou',\n",
       " 'hua',\n",
       " 'hui',\n",
       " 'hun',\n",
       " 'huo',\n",
       " 'jia',\n",
       " 'jie',\n",
       " 'jin',\n",
       " 'jiu',\n",
       " 'jue',\n",
       " 'kai',\n",
       " 'kan',\n",
       " 'kao',\n",
       " 'ken',\n",
       " 'kou',\n",
       " 'kua',\n",
       " 'kui',\n",
       " 'kun',\n",
       " 'kuo',\n",
       " 'lai',\n",
       " 'lan',\n",
       " 'lao',\n",
       " 'lei',\n",
       " 'lia',\n",
       " 'lie',\n",
       " 'lin',\n",
       " 'liu',\n",
       " 'lou',\n",
       " 'lun',\n",
       " 'luo',\n",
       " 'lve',\n",
       " 'mai',\n",
       " 'man',\n",
       " 'mao',\n",
       " 'mei',\n",
       " 'men',\n",
       " 'mie',\n",
       " 'min',\n",
       " 'miu',\n",
       " 'mou',\n",
       " 'nai',\n",
       " 'nan',\n",
       " 'nao',\n",
       " 'nei',\n",
       " 'nen',\n",
       " 'nie',\n",
       " 'nin',\n",
       " 'niu',\n",
       " 'nou',\n",
       " 'nun',\n",
       " 'nuo',\n",
       " 'nve',\n",
       " 'pai',\n",
       " 'pan',\n",
       " 'pao',\n",
       " 'pei',\n",
       " 'pen',\n",
       " 'pie',\n",
       " 'pin',\n",
       " 'pou',\n",
       " 'qia',\n",
       " 'qie',\n",
       " 'qin',\n",
       " 'qiu',\n",
       " 'que',\n",
       " 'qun',\n",
       " 'ran',\n",
       " 'rao',\n",
       " 'ren',\n",
       " 'rou',\n",
       " 'rua',\n",
       " 'rui',\n",
       " 'run',\n",
       " 'ruo',\n",
       " 'sai',\n",
       " 'san',\n",
       " 'sao',\n",
       " 'sen',\n",
       " 'sha',\n",
       " 'she',\n",
       " 'shi',\n",
       " 'shu',\n",
       " 'sou',\n",
       " 'sui',\n",
       " 'sun',\n",
       " 'suo',\n",
       " 'tai',\n",
       " 'tan',\n",
       " 'tao',\n",
       " 'tei',\n",
       " 'tie',\n",
       " 'tou',\n",
       " 'tui',\n",
       " 'tun',\n",
       " 'tuo',\n",
       " 'wai',\n",
       " 'wan',\n",
       " 'wei',\n",
       " 'wen',\n",
       " 'xia',\n",
       " 'xie',\n",
       " 'xin',\n",
       " 'xiu',\n",
       " 'xue',\n",
       " 'xun',\n",
       " 'yan',\n",
       " 'yao',\n",
       " 'yin',\n",
       " 'you',\n",
       " 'yue',\n",
       " 'yun',\n",
       " 'zai',\n",
       " 'zan',\n",
       " 'zao',\n",
       " 'zei',\n",
       " 'zen',\n",
       " 'zha',\n",
       " 'zhe',\n",
       " 'zhi',\n",
       " 'zhu',\n",
       " 'zou',\n",
       " 'zui',\n",
       " 'zun',\n",
       " 'zuo',\n",
       " 'ai',\n",
       " 'an',\n",
       " 'ao',\n",
       " 'ba',\n",
       " 'bi',\n",
       " 'bo',\n",
       " 'bu',\n",
       " 'ca',\n",
       " 'ce',\n",
       " 'ci',\n",
       " 'cu',\n",
       " 'da',\n",
       " 'de',\n",
       " 'di',\n",
       " 'du',\n",
       " 'en',\n",
       " 'er',\n",
       " 'fa',\n",
       " 'fo',\n",
       " 'fu',\n",
       " 'ga',\n",
       " 'ge',\n",
       " 'gu',\n",
       " 'ha',\n",
       " 'he',\n",
       " 'hu',\n",
       " 'ji',\n",
       " 'ju',\n",
       " 'ka',\n",
       " 'ke',\n",
       " 'ku',\n",
       " 'la',\n",
       " 'le',\n",
       " 'li',\n",
       " 'lo',\n",
       " 'lu',\n",
       " 'lv',\n",
       " 'ma',\n",
       " 'me',\n",
       " 'mi',\n",
       " 'mo',\n",
       " 'mu',\n",
       " 'na',\n",
       " 'ne',\n",
       " 'ni',\n",
       " 'nu',\n",
       " 'nv',\n",
       " 'ou',\n",
       " 'pa',\n",
       " 'pi',\n",
       " 'po',\n",
       " 'pu',\n",
       " 'qi',\n",
       " 'qu',\n",
       " 're',\n",
       " 'ri',\n",
       " 'ru',\n",
       " 'sa',\n",
       " 'se',\n",
       " 'si',\n",
       " 'su',\n",
       " 'ta',\n",
       " 'te',\n",
       " 'ti',\n",
       " 'tu',\n",
       " 'wa',\n",
       " 'wo',\n",
       " 'wu',\n",
       " 'xi',\n",
       " 'xu',\n",
       " 'ya',\n",
       " 'ye',\n",
       " 'yi',\n",
       " 'yo',\n",
       " 'yu',\n",
       " 'za',\n",
       " 'ze',\n",
       " 'zi',\n",
       " 'zu',\n",
       " 'a',\n",
       " 'e',\n",
       " 'o']"
      ]
     },
     "execution_count": 203,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pinyin_all"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 218,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 查找正确的拼音组合\n",
    "def split_sentence(sentence):\n",
    "    result = []\n",
    "    find_index=[]\n",
    "    find_word = ''\n",
    "    index = -1\n",
    "    if(len(sentence) == 1):\n",
    "        return [sentence]\n",
    "    if(len(sentence) == 0):\n",
    "        return []\n",
    "    for word in pinyin_all:\n",
    "        index = sentence.find(word)\n",
    "        if index != -1:\n",
    "            find_index.append((word, index))\n",
    "        if index == 0:\n",
    "            find_word = word\n",
    "            break;\n",
    "    if index == 0:\n",
    "        result.append(find_word)\n",
    "        result += split_sentence(sentence[len(word):len(sentence)])\n",
    "    else:\n",
    "        (word,index) = min(find_index, key=lambda x:x[1])\n",
    "        find_word = sentence[0:index+len(word)]\n",
    "        result.append(find_word)\n",
    "        result += split_sentence(sentence[index+len(word):len(sentence)])\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 219,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['wo', 'xiang', 'shang', 'qing', 'hua', 'xda', 'xue']"
      ]
     },
     "execution_count": 219,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sentence = 'woxiangshangqinghuaxdaxue'\n",
    "split_sentence(sentence)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 220,
   "metadata": {},
   "outputs": [],
   "source": [
    "def correct_sentence(sentence):\n",
    "    words = split_sentence(sentence)\n",
    "    new_sentence = ''\n",
    "    for word in words:\n",
    "        new_sentence += (word + ' ')\n",
    "    return correct_sequence_pinyin(new_sentence[0:-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 221,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'wo xiang shang qing hua da xue'"
      ]
     },
     "execution_count": 221,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "correct_sentence('woxiangshangqinghuaxdaxue')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 222,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'wo xiang sha qin hua da xue'"
      ]
     },
     "execution_count": 222,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "correct_sentence('woxiangshagnqinnghuadaxue')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 223,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'zhe si yi ge ce shi'"
      ]
     },
     "execution_count": 223,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "correct_sentence('zhesihyigecesho')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
